package org.meichao.demo.service.algorithms;

/**
 * 最大公约数
 */
public class GCD {

    public static void main(String[] args) {
        //辗转相除法
        getGreatestCommonDivisor(10, 25);
        //更相减损术
        gcd1(10, 25);
    }

    /**
     * 辗转相除法
     * @param a
     * @param b
     * @return
     */
    public static int getGreatestCommonDivisor(int a, int b){
        int result = 1;
        if(a > b){
            result = gcd(a, b);
        }else {
            result = gcd(b, a);
        }
        return result;
    }

    /**
     * 两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
     * 比如10和25，25除以10商2余5,那么10和25的最大公约数，等同于10和5的最大公约数
     * @param a
     * @param b
     * @return
     */
    public static int gcd(int a, int b){
        if(a%b == 0){
            return b;
        }
        return gcd(b, a % b);
    }

    /**
     * 更相减损术
     * 两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。
     * 比如10和25，25减去10的差是15,那么10和25的最大公约数，等同于10和15的最大公约数。
     * @param a
     * @param b
     * @return
     */
    public static int gcd1(int a, int b){
        if(a == b){
            return a;
        }
        if (a < b) {
            return gcd1(b - a, a);
        }else
            return gcd1(a - b, b);
    }

}
